package 学习计划.数据结构;

/**
 * @author 会玩的洋洋
 * https://leetcode.cn/problems/sort-colors/?envType=study-plan&id=shu-ju-jie-gou-ji-chu&plan=data-structures&plan_progress=cqjfoh6
 */
public class _75_颜色分类 {

    /**
     * 执行用时：0ms，内存消耗：40.1MB
     * @param nums
     */
    public void sortColors(int[] nums) {
        int n = nums.length;
        int target = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                swap(nums, target, i);
                target++;
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] == 1) {
                swap(nums, target, i);
                target++;
            }
        }
    }

    /**
     * 执行用时：0ms，内存消耗：39.9MB
     * @param nums
     */
    public void sortColors2(int[] nums) {
        int n = nums.length;
        int p0 = 0, p1 = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 1) {
                swap(nums, p1, i);
                p1++;
            } else if (nums[i] == 0) {
                swap(nums, p0, i);
                if (p0 < p1) {
                    swap(nums, p1, i);
                }
                p1++;
                p0++;
            }
        }
    }

    /**
     * 执行用时：0ms, 内存消耗：40.1MB
     * @param nums
     */
    public void sortColors3(int[] nums) {
        int n = nums.length;
        int p0 = 0, p2 = n - 1;
        for (int i = 0; i < n; i++) {
            while (i <= p2 && nums[i] == 2) {
                swap(nums, p2, i);
                --p2;
            }

            if (nums[i] == 0) {
                swap(nums, p0, i);
                p0++;
            }
        }
    }
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
